
public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null){
            return null;
        }

        ListNode odd = head;
        ListNode even = head.next;
        ListNode headA = new ListNode(-1);
        ListNode headB = new ListNode(-1);
        ListNode curA = headA;
        ListNode curB = headB;
        while(even != null && even.next != null){
            curA.next = odd;
            curA = odd;
            odd = odd.next.next;
            curB.next = even;
            curB = even;
            even = even.next.next;
        }
        if(even != null){
            curA.next = odd;
            curA = odd;
            curB.next = even;
            curB = even;
        }else{
            curA.next = odd;
            curA = odd;
        }
        curA.next = headB.next;
        curB.next = null;
        return headA.next;
    }
}